//小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为
// root 。 
//
// 除了
// root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的
//房子在同一天晚上被打劫 ，房屋将自动报警。 
//
// 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: root = [3,2,3,null,3,null,1]
//输出: 7 
//解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7 
//
// 示例 2: 
//
// 
//
// 
//输入: root = [3,4,5,1,3,null,1]
//输出: 9
//解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
// 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 树的节点数在 [1, 10⁴] 范围内 
// 0 <= Node.val <= 10⁴ 
// 
//
// Related Topics 树 深度优先搜索 动态规划 二叉树 👍 1802 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-09-18 09:29:52
 * @description 337.打家劫舍 III
 */
public class HouseRobberIii{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new HouseRobberIii().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

// Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
		 //f是选，g是不选
		 Map<TreeNode,Integer> f=new HashMap<>();
		 Map<TreeNode,Integer> g=new HashMap<>();
    public int rob(TreeNode root) {
		dfs(root);
		return Math.max(f.getOrDefault(root,0),g.getOrDefault(root,0));
    }
	private void dfs (TreeNode root){
		if(root==null){
			return;
		}
		dfs(root.left);
		dfs(root.right);
		//后续遍历，每一层的最大值是
		//o被选中，f(0)=g(l)+g(r)
		//o不被选中, g(o)=max{f(l),g(l)}+max{f(r),g(r)}
		f.put(root,root.val+g.getOrDefault(root.left,0)+g.getOrDefault(root.right,0));
		g.put(root,Math.max(f.getOrDefault(root.left,0),g.getOrDefault(root.left,0))+Math.max(f.getOrDefault(root.right,0), g.getOrDefault(root.right, 0)));
	}

	/*空间优化，f(o)和g(o)只和他的左右值有关*/
	public int rob1(TreeNode root){
		int [] rootStatus=dfs1(root);
		return Math.max(rootStatus[0],rootStatus[1]);
	}
	//0 不偷，1偷
	private int[] dfs1(TreeNode root){
		if(root==null)return new int[]{0,0};
		int []l=dfs1(root.left);
		int[] r=dfs1(root.right);
		int selected=root.val+l[1]+r[1];
		int notSelected=Math.max(l[0],l[1])+Math.max(r[0],r[1]);
		return new int[]{selected,notSelected};
	}
		/*浅显易懂*/
	public int rob2(TreeNode root) {
		if (root == null) return 0;

		int money = root.val;
		if (root.left != null) {
			money += (rob(root.left.left) + rob(root.left.right));
		}

		if (root.right != null) {
			money += (rob(root.right.left) + rob(root.right.right));
		}

		return Math.max(money, rob(root.left) + rob(root.right));
	}
	/**/
	public int rob3(TreeNode root) {
		HashMap<TreeNode, Integer> memo = new HashMap<>();
		return robInternal(root, memo);
	}
	/*记忆化搜索*/
	public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) {
		if (root == null) return 0;
		if (memo.containsKey(root)) return memo.get(root);
		int money = root.val;

		if (root.left != null) {
			money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
		}
		if (root.right != null) {
			money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
		}
		int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
		memo.put(root, result);
		return result;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
